package com.ting.test.algorithms.前缀树;


import java.util.HashMap;

/**
 * next数组 一共26个元素，从0到25，每一个下标代表一个字母
 */
public class TrieTree2 {
    private char base = 'a';
    private NodeWithHashMap root;

    /**
     * 注意在操作时 root节点只作为跟节点 并不代表任何字母
     */
    public TrieTree2() {
        this.root = new NodeWithHashMap();
    }


    public boolean insert(String word) {
//        if (StringUtils.isEmpty(word)) {
//            return false;
//        }
        char[] chars = word.toCharArray();
        NodeWithHashMap node = root;
        node.pass++;
        for (char current : chars) {
            int index = current - base;
            HashMap<Integer,NodeWithHashMap> next = node.next;
            if (!next.containsKey(index)) {
                next.put(index,new NodeWithHashMap());
            }
            NodeWithHashMap nodeWithHashMap = next.get(index);
            nodeWithHashMap.pass++;
            node =nodeWithHashMap;
        }
        node.end++;
        return true;
    }


    /**
     * 查找字符串是否在线段树中，并返回该字符串被添加过几次
     *
     * @param word
     * @return
     */
    public int search(String word) {
        if (word==null) {
            return 0;
        }
        char[] chars = word.toCharArray();
        NodeWithHashMap node = root;
        node.pass++;
        for (char current : chars) {
            int index = current - base;
            HashMap<Integer,NodeWithHashMap> next = node.getNext();
            // 如果字符串嗨没匹配完，但是next数组中没有下一个字符 说明字符串不存在
            if (!next.containsKey(index)) {
                return 0;
            }
            node = next.get(index);
        }
        return node.end;
    }


    public boolean delete(String word) {
        //先判断字符串是否在前缀树中，在才会删除
        if (search(word) == 0) {
            return false;
        }

        char[] chars = word.toCharArray();
        NodeWithHashMap node = root;
        node.pass++;
        for (char current : chars) {
            int index = current - base;
            HashMap<Integer,NodeWithHashMap> next = node.next;
            next.get(index).pass--;
            node = next.get(index);
        }
        node.end--;
        return true;
    }

    /**
     * 		// 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
     * @param word
     * @return
     */
    public int prefixNumber(String word) {
        if (word==null) {
            return 0;
        }
        char[] chars = word.toCharArray();
        NodeWithHashMap node = root;
        node.pass++;
        for (char current : chars) {
            int index = current - base;
            HashMap<Integer,NodeWithHashMap> next = node.getNext();
            // 如果字符串嗨没匹配完，但是next数组中没有下一个字符 说明字符串不存在
            if (!next.containsKey(index) ) {
                return 0;
            }
            node =next.get(index);
        }
        return node.pass;
    }


}
